package com.mango.data.structure.hash;

import java.util.*;

/**
 * HashSet实现
 * @Author: mango
 * @Date: 2022/5/21 10:48 下午
 */
public class HashSet<V> implements Set<V> {
    private Node<V>[] array;
    // 容量
    private int capacity;
    // 大小
    private int size;
    // 默认容量
    private int DEFAULT_CAPACITY = 8;
    // 负载因子
    private double LOAD_FACTOR = 0.75;

    @Override
    public Object[] toArray() {
        Object[] arr = new Object[size];
        int count = 0;
        for(int i=0;i<capacity;i++){
            Node<V> node = array[i];
            if(node != null){
                arr[count++] = node.val;
                while (node.next != null){
                    arr[count++] = node.next.val;
                    node = node.next;
                }
            }
        }
        return arr;
    }

    private void copy(Object[] a, Object[] b){
        int count = Math.min(a.length,b.length);
        for(int i=0;i<count;i++){
            b[i] = a[i];
        }
    }

    @Override
    public <T> T[] toArray(T[] a) {
        copy(toArray(),a);
        return a;
    }

    @Override
    public Iterator<V> iterator() {
        Object[] arr = toArray();
        int size = arr.length;
        Iterator<V> iterator = new Iterator<V>() {
            int cursor = 0;
            @Override
            public boolean hasNext() {
                return cursor < size;
            }

            @Override
            public V next() {
                return (V) arr[cursor++];
            }
        };
        return iterator;
    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean contains(Object o) {
        return getNode(hash(o), (V) o) != null ? true : false;
    }

    private void resize(){
        int m = (int) (capacity * LOAD_FACTOR / 2);
        // 超过负载，则扩容
        if(size / capacity > LOAD_FACTOR){
            resize(1);
            System.out.println("扩容");
        }
        // 低于负载的一半，且缩减后的容量不小于默认容量，则缩容
        else if(size < m && m >= (DEFAULT_CAPACITY / 2) ){
            resize(0);
            System.out.println("缩容");
        }
    }

    // 扩容,缩容
    private void resize(int flag){
        int oldCapacity = capacity;
        Node<V>[] oldArray = this.array;
        if(flag == 1) {
            this.capacity = this.capacity << 1;
        }else{
            this.capacity = this.capacity >> 1;
        }
        this.array = new Node[capacity];
        this.size = 0;
        for(int i=0;i<oldCapacity;i++){
            Node<V> node = oldArray[i];
            if(node != null){
                addVal(node.val);
                while (node.next != null){
                    addVal(node.next.val);
                    node = node.next;
                }
            }
        }
    }

    private Node<V> getNode(int hash, V val){
        int index = hash % capacity;
        if(array[index] == null){
            return null;
        }else{
            Node<V> node = array[index];
            while (node != null && !node.val.equals(val)){
                node = node.next;
            }
            if(node != null){
                return node;
            }
        }
        return null;
    }

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    private void addVal(V val){
        int index = hash(val) % capacity;
        Node<V> node = array[index];
        // 如果存在，则跳过
        if(contains(val)){
            return ;
        }
        // 不存在，则加入
        if(node == null){
            array[index] = new Node(val);
        }else{
            while (node.next != null){
                node = node.next;
            }
            node.next = new Node(val);
        }
        size++;
    }

    @Override
    public boolean add(V v) {
        // 如果为空，则先创建默认容量大小的数组
        if(array == null){
            this.array = new Node[DEFAULT_CAPACITY];
            this.capacity = DEFAULT_CAPACITY;
        }
        // 设置值
        addVal(v);
        // 控制容量
        resize();
        return true;
    }

    @Override
    public boolean remove(Object o) {
        if(contains(o)){
            int index = hash(o) % capacity;
            if(array[index] != null){
                Node<V> node = array[index];
                if(node.next == null){
                    array[index] = null;
                }else{
                    while (node.next != null && !node.next.val.equals(o)){
                        node = node.next;
                    }
                    node.next = node.next.next;
                }
                size--;
                // 控制容量
                resize();
            }
        }
        return true;
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        boolean result = true;
        for(Object o : c){
            if(!contains(o)){
                result = false;
                break;
            }
        }
        return result;
    }

    @Override
    public boolean addAll(Collection<? extends V> c) {
        c.forEach(e-> addVal(e));
        return true;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        return false;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        c.forEach(e-> remove(e));
        return true;
    }

    @Override
    public void clear() {
        this.size = 0;
        this.capacity = 0;
        this.array = null;
    }

    /**
     * 链表节点
     */
    final class Node<V> {
        public V val;
        public Node<V> next;

        public Node(V val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }

    @Override
    public String toString() {
        return "HashSet{" +
                "array=" + Arrays.toString(array) +
                ", capacity=" + capacity +
                ", size=" + size +
                '}';
    }
}
